public class Test {
    import java.util.*;


    public class Solution {
        /**
         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
         *
         *
         * @param a int整型一维数组
         * @param n int整型
         * @param K int整型
         * @return int整型
         */
        public int findKth (int[] a, int n, int K) {
            // write code here
            return qsort(a,0,n-1,K);
        }
        public int qsort(int[] nums,int l,int r,int k) {
            //生成随机数
            int key = nums[(l+r)/2];
            int left = l-1 , right = r+1,i = l;
            //划分区域
            while(i < right) {
                if(nums[i] < key) {
                    swap(nums,++left,i++);
                } else if(nums[i] == key) {
                    i++;
                } else {
                    swap(nums,--right,i);
                }
            }
            //区间成型
            //[l,left],[left+1,right-1],[right,r]
            int c = r-right+1 , b = right -left -1 ;
            if(c >= k) {
                return qsort(nums,right,r,k);
            } else if (b+c >= k) {
                return key;
            }else{
                return qsort(nums,l,left,k-c-b);
            }
        }
        public void swap(int[]nums,int l ,int r) {
            int tmp = nums[l];
            nums[l] = nums[r];
            nums[r] = tmp;
        }
    }
}
